package java;

public class Question5 {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("adsadaa"));
    }
    public static String longestPalindrome(String s) {
        int sLength = s.length();
        String max = "";
        boolean[][] isPalindrome = new boolean[sLength + 1][sLength + 1];
        for (int j = 0;j < sLength + 1; j ++){
            for (int i = j ; i >= 0 ;i --){
                if (i == j || i == j - 1){
                    isPalindrome[i][j] = true;
                }else if (s.charAt(i) == s.charAt(j - 1) && isPalindrome[i + 1][j - 1]){
                    isPalindrome[i][j] = true;
                }else {
                    isPalindrome[i][j] = false;
                }
                if (i != j && isPalindrome[i][j] && max.length() < j - i){
                    max = s.substring(i,j);
                }
            }
        }
        return max;
    }
}
